#include <iostream>
#include <vector>


std::vector<std::vector<int> > res;


void backtrack(int nums[], int len, int target, std::vector<int> &track, int index)
{

    //回溯法
    //路径：数组里面已经选择过的
    //选择列表：数组里面的当前数字
    //结束条件：到了数组的最后一个数字，且和为target

    //判断是否达到结束条件
    if (index == len)
    {
        int sum = 0;
        for (unsigned int i = 0; i < track.size(); i++)
        {
            sum += track[i];
        }
        if (sum == target)
        {
            std::vector<int> temp(track);
            res.push_back(temp);       
        }
        return;
    }
    /*
    for 选择 in 选择列表:
    这里的选择应该是对当前的数字选择 + 还是 选择 -
    nums[]中的数字依次只能一个，这不是可供选择的，而是自然的
    */
    track.push_back(nums[index]);
    backtrack(nums, len, target, track, index + 1);
    track.pop_back();
    track.push_back(nums[index]*(-1));
    backtrack(nums, len, target, track, index + 1);
    track.pop_back();
}
int main()
{
    using namespace std;

    int nums[20] = {25,29,23,21,45,36,16,35,13,39,44,15,16,14,45,23,50,43,9,15};
    int len = 20;
    int target = 32;
    std::vector<int> track;
    backtrack(nums, len, target, track, 0);
    cout << res.size() << endl;
    /*
    for (unsigned int i = 0; i < res.size(); i++)
    {
        for (unsigned int j = 0; j < res[i].size(); j++)
        {
            cout << res[i][j] << " " ;
        }
        cout << endl;
    }
    */
    return 0;
}